\section{Tutorial}

The DiGr programming is designed to make creating, modifying and
inspecting directed graphs easy and efficient. It provides tools for constructing trees, and an extensible traversal framework. This tutorial will walk you through the basis of DiGr, but will necessarily leave some details out. For more information, please see the reference manual below. 

\subsection{Basics}

DiGr is built on a C-like base. Each program begins execution in an
opt with no arguments called {\tt main}, declared as follows :

\begin{Verbatim}
opt main(){

	...program code..
}
\end{Verbatim}

Your running program will start within these brackets.

DiGr has 5 variable types: integers, floating point numbers, strings,
nodes and edges.  The first 3 types are simple data types, similar to
variables in other languages.  Nodes and edges are more complex
variable types that we will get to later.

First let's start with a simple statement that does something in the
DiGr language.

\begin{Verbatim}
opt main(){

	print("Hello World")!
}
\end{Verbatim}

print is a simple operation call that takes its contents, a string
"hello world" in this case, and displays it on the console.  A program
consists of multiple statements like this, each ending in an
exclamation mark.

To store values for later use we have variables.  Declare a new
variable in the form:

\begin{Verbatim}
type Variable_name1!
\end{Verbatim}

Type can be str, flt, int, node or edge.  The variable name must start
with either a lower or upper case character, and consist of any number
of underscores, characters or numbers.  The following statement
declares a string variable.

\begin{Verbatim}
str MyString1!
\end{Verbatim}

Set a variable to a certain value with the '=' symbol, either while
declaring it or any time afterward.

\begin{Verbatim}
str MyString = "DiGr"!
MyString = "Program"!
\end{Verbatim}

To store a collection of values in one symbol, use an array.  An array
is declared with a set size.  Once declared,the size cannot be
changed.  The following example illustrates an array of integers with
size 5 being declared:

\begin{Verbatim}
int MyIntArray[5]!
\end{Verbatim}

You can initialize an array on declaration by assigning a bracket
enclosed list of values of the appropriate type.  Not the length of
the list must not exceed the length of the array

\begin{Verbatim}
int myList[5] = {1;2;3;4;5}!
\end{Verbatim}

\subsection{Loops and Conditions}

Iteration is handled with the while loops, which take conditional
statements like:

\begin{itemize}
\item {\tt value == value} : check to see if the values are equal.
\item {\tt value != value} : check to see if the values are not equal.
\end{itemize}

and the scalar comparisons $<$, $>$ , $<=$ , $>=$.  Anything within
the body of the while loop runs while these conditions hold.  The
following example illustrates the while loop:

\begin{Verbatim}
while (myInt != 1)
{
	myInt = myInt - 1!
} 
\end{Verbatim}

For control logic we have if else statements.  Like other languages,
we check a condition within the if statement and run the first block
if statements if it evaluates to true, and the else block if the
statement evaluates to false.  The else block is optional.  We can see
its use in the following lines of code.

\begin{Verbatim}
if(myVal ==5)
{
	newValue = 5!
}
else
{
	newValue = 6!
}
\end{Verbatim}

\subsection{User Defined Operations}

You can also declare operations to serve as functions.  We declare
these with the opt label, name and arguments.  Arguments have a
direction type, either in or out, a data type, and a name within the
scope of the operation.  Operation declaration cannot be nested.  They
are declared outside of opt main and can be referenced in any code
before or after the opt declaration.  The following is an example of
an operation function.

\begin{Verbatim}
opt addThree(in int n; out int return)
{
	return = n + 3!
}
\end{Verbatim}

This operation takes the value n, adds 3 to it and pass it back to the
caller in the return variable.  The following code calls it:

\begin{Verbatim}
opt main(){
	
	int m!
	addThree(3;m)!
	print(m)! : This prints 6	
}
\end{Verbatim}

Note that the argument passed must be a variable, as the operation
sets its value.

\subsection{Graphs}

Now to get to the real strength of DiGr, the node and edge types, and
their traversal.  Node objects represent vertices in a graph, and an
edge object is used to connect them.  DiGr can connect two nodes with
a simple statement.


\begin{Verbatim}
node1 -> node2!
\end{Verbatim}

We have now created an edge between node1 and node2.  The $->$
indicates that this is a directed edge, out from node1, in to node2.
We could have done the reverse with the following statement:

\begin{Verbatim}
node1 <- node2!
\end{Verbatim}

or

\begin{Verbatim}
node2 -> node1!
\end{Verbatim}

If we wanted an undirected edge, we could use:

\begin{Verbatim}
node1 -- node2!
\end{Verbatim}

There is an easier, quicker way to create edges between nodes.  Using
an array of nodes you can create what we call a Connection Context.
In a single line of code we can connect any number of nodes with any
type of connections within the array.  The following line of code will
show you how:

\begin{Verbatim}
int myNodeArray[5] = |0 -> (2->4), 3 |!
\end{Verbatim}

With this one line of code we have created 3 connections between 4
nodes.  The connection context is enclosed within the | | symbols.
The numbers here reference the nodes at the array index.  You can see
the edge type between them.  A comma after an integer or parenthesized
unit allows us to connect the first node to multiple nodes with the
same kind of edge.  See the Language reference manual for more
details.
 
We will be able to utilize these edge types with crawl operations on
these nodes. Node objects have built in special properties which you
can access by {\tt nodevariable.property}.

\begin{itemize}
\item {\tt myNode.parent(n)} : gives you the nth node that has a
  directed edge into myNode

\item {\tt myNode.child(n)}: the same thing as parent but the edge
  direction is reversed

\item {\tt myNode.inedges} and {\tt myNode.outedges} both return just
  the number of those types of edges connected to myNode.  

\item You can retrieve those edges with the {\tt node.outedge(n)} and
  {\tt node.inedge(n)} properties, similar to the parent and child
  properties.
\end{itemize}

You can also define your own properties for a node with the following
line of code.

\begin{Verbatim}
myNode.weight = 5!
\end{Verbatim}

These attributes must be integers.  If you attempt to reference an
attribute that has not already been defined, the value will be 0.

Edge objects are similar in a lot of ways to the node object.  They
are implicitly created when you create a node connection, but can be
declared independently in their own variable.  Edges are declared with
the edge type.  They have properties similar to the node, that can
access the nodes they are connecting.  Additionally, they can be given
additional properties in the same way as nodes.

\subsection{Graph Traversal}

To really make the most use of these connections we can use a crawl.
A crawl is defined like a function, with {\tt crawl name(args)} rather
than {\tt opt name(args)}.  The body of the crawl itself usually only
operates on a single node, though implicit in a crawl is a graph
traversal function.  The crawl moves through nodes that have been
connected in the direction of their edges.  It uses a queue to
determine the order of the traversal, and calls a rule object (see
below) to determine what (if anything) to add to the queue.

A crawl has two special key words to handle the traversal.  The {\tt
  current} symbol represents the node that the crawl is currently on.
The {\tt call} imperative executes the rule, which may or may not add
any additional nodes to the queue.

Here is a very basic crawl which does not make use of its rule:

\begin{Verbatim}
crawl myCrawl(in int compareValue)
{
	if(current.weight == compareValue)
	{
		print("this is the right node")!
	}

}
\end{Verbatim}

This crawl compares the current node's weight property with the value
passed to the crawl.  If these matches, it prints a message. To start
a crawl, you call it like an opt but with additional special
arguments.

\begin{Verbatim}
opt myOpt(){

	myCrawl(5) from myNode with myRule!

}
\end{Verbatim}

The from-with statement at the end handle two additional arguments.
myNode is the starting point, the first node to be processed with the
crawl.

myRule is a rule, a special object that guides the crawl.  A rule is
declared like a function, but has no arguments.

\begin{Verbatim}
rule myRule{
	..rule code..
}
\end{Verbatim}

A rule's job is to decide which nodes are queued up for the crawl.

It has some special functions which manage the queue.  It also has the
{\tt current} handle which points to the node the crawl is at.  It can
add a node to the queue with the {\tt add(node)} function and add to
the front of the queue with the {\tt addFront(node)} function.  In
each case the argument passed must be a variable of type node.

%For a more general queuing algorithm we have the functions {\tt addBy}
%and {\tt addByFront}. You pass these functions the property to be
%assessed, in the form object\_type.attribute, where object is either
%node or edge and the attribute is an attribute belonging to that
%object.  The second argument is the value assertion, and the third
%argument is the number of nodes to queue.  The following illustrates
%its uses.

%rule add3Heaviest{%
%	addBy(node.weight;\$;3)
%}

%node.weight indicates that the node's weight is the attribute being
%assessed, \$ says that we want to add the nodes with the largest
%weight to the queue first.  3 says we will only add 3 nodes at a time
%to the queue.  Alternatively we could have passed an edge, or a
%different attribute.  For the second argument we could have used the
%~ symbol, to indicate we want to add the nodes with the smallest
%weight.  We could have passed 0 for the last argument to say we want
%to add all children nodes

%It is important to note a few things about these methods, since they
%are meant to be used heavily.  First, addby only considers the
%children of a node as candidates for the queue.  Second, if the first
%argument is assessing an edge property, the next node is on the
%inbound side of that edge.




Now that we have some idea as to what the rule is we can put the crawl
and rule together.  When the crawl runs and reaches the end of the
body of statements, it looks at the first node in the queue.  If there
is something on the queue, it runs again, with this new node set to
the {\tt current} handle.  Within the crawl you can add new nodes to
the queue by invoking the rule with the {\tt call} command.  This adds
nodes to the queue according to the rule set.  You can also change the
rule with the {\tt set} command.  The following examples illustrates
both of these commands.

\begin{Verbatim}
crawl newCrawl(in int someVar)
{
 	call! :add new nodes to the queue, if applicable. :
	set(newRule)! :change the way we add nodes to the queue :
	call! : add new nodes with the new rule :
}
\end{Verbatim}

And there you have it.  Within the crawl we can modify or output
variables within a graph.  And we use a rule to make traversal of this
graph as simple as possible.

To put all the pieces together now, we have 3 code block types, the
crawl, rule and opt.  Opts are general functions with one main
function for the program, crawls are specialized operations with
iteration built in, and rules guide the crawls.  

Hopefully these tools will be helpful to you in any graph related
problem solving. There are subtleties in the language we have glossed
over here. For further information, see the language reference manual below.
